Recipe

Introduction

Travelling Sales Person

TSP (Travelling Sales Person) – Route Planning

Route planning is a generic problem which involves the optimization of the journey around a network of points. Problems in this category involve optimization of traffic in telecommunications networks and optimization of routes in the distribution sector. A classic problem in this category is the travelling salesperson problem (TSP), where there is a need to minimise the distance travelled by the salesperson while visiting a number of cities.

The TSP application included with the sample applications is an implementation of this problem using Knowledge Builder. In TSP, the number of UK cities to be visited is 12. View the optimization object TSP_Opt. Observe the chromosome definition which is 12 sequenced genes. Each gene represents a city number from 1 to 12 and the order of the genes will reflect the order of visiting the 12 cities. The genes are mapped onto the Knowledge Builder array Gene_Visit_Order[1..12]. The Procedure Build_Data is called from the Optimisation Start event and builds up the matrix of distances into a Knowledge Builder array then initialises a number of variables. The script commands of the Procedure TSP_UK_PRC_VB calculate the total distance travelled for a particular sequence of genes.

With the default optimization parameters, TSP can find the optimal route of 1320 miles in under 175 generations.

In the Tsp_Adaptation Knowledge Module an adaptation strategy is used. Adaptation strategy involves the adjustment of the optimisation parameters dynamically during the optimisation process and this sample increases the mutation probability after a number of generations have failed to improve the cost. The logic being that if the system is failing to find a better result then adding more randomness may pop up a better individual and cause the system to start to explore in a new area of the search space.

In Tsp_Adaptation the mutation probability is changed during the optimisation process so the original value is stored in the variable Start_Mutation_Level in event Optimisation Start. Also the variable prevCost is initialised to a number that is higher than any possible cost result. The Generation End event code is shown below:

Function ( genNo:N , bestCost:N , avgCost:N ) : B
@Return TRUE
@If bestCost < prevCost
  @Assign prevCost = bestCost
  @Assign CostCount = 0
  @Assign TSP_Opt.mutation = Start_Mutation_Level
@Else
  @Assign CostCount = CostCount + 1
  @If CostCount = 10
     @Assign TSP_Opt.mutation = TSP_Opt.mutation + (Start_Mutation_Level / 4)
     @Assign CostCount = 0
  @EndIf
@EndIf

If the system fails to improve the cost for 10 generations the mutation probability is increased by Start_Mutation_Level / 4. If the cost has not improved after a further 10 generations then the mutation probability is increased again and so on. Every time the cost is improved the mutation probability is reset to its original pre-set value and the counter (CostCount) set to zero.

TSP Script Commands:

You can examine the use of these specific Knowledge Builder procedural @commands used, by looking in these Procedure objects within the application.